約 3,731,652 件
https://w.atwiki.jp/isoroku_be/pages/109.html
情報 作者名:ゆちボン 引用元:なでしこプログラム掲示板「なでしこでソートプログラム集」 解説引用元:http //ja.wikipedia.org/wiki/コムソート リンク:●バブルソート、●双方向バブルソート、●おいこみソート 概要 コムソート(Comb Sort)は、ソートのアルゴリズムの一つ。コームソート、櫛(くし)ソートなどとも呼ばれる。 バブルソートの改良版。内部ソートだが、安定ソートではない。 安定:× 速度:ほぼ、o(n log n) 解説 ちなみに、コムソート11を使用してます。 コムソート11を使用しない場合は「※」がついている行を コメントアウトしてくんさい。 ※コムソート11とは? gap=9,10となったとき、強制的にgap=11とすることで高速化したアルゴリズムを、Comb sort 11と呼ぶ。 gapが9→6→4→3→2→1や10→7→5→3→2→1と遷移するよりも、11→8→6→4→3→2→1と遷移する方がうまく櫛が梳けるためである。 サンプルプログラム 200回、テスト[回数-1]は乱数(200) テストをコムソート。 テストをメモ記入。 おわり //本体 ●コムソート(Aを) max=配列要素数(A) 処理開始 gap=max (gap 0)の間 gap=INT(gap/1.3) もし、gap=9||gap=10なら、gap=11 ※ i=0 (i+gap max)の間 もし、A[i+gap] A[i]なら tmp=A[i+gap] A[i+gap]=A[i] A[i]=tmp i=i+1 Aで戻る。 掲載ありがとうございます!コムソート11の解説のところですが、本体のプログラムでは「h」ではなく「gap」という変数にしていますので、そちらにしていただけるとわかりやすいと思います。 -- ゆちボン (2008-10-14 17 07 02) 修正しましたー!ありがとうございますー! -- 管理人 (2008-10-14 20 01 06) 名前 コメント
https://w.atwiki.jp/isoroku_be/pages/112.html
情報 作者名:ゆちボン 引用元:なでしこプログラム掲示板「なでしこでソートプログラム集」 リンク:●コムソート、●バブルソート、●双方向バブルソート 概要 正式名称不明。 僕は「最大最小値ソート」「おいこみソート」と呼んでいます。 バブルソートの改良型で、1回のスキャンで最大値、最小値を見つけて、最後に交換します。 繰り返す量はバブルの半分。 安定:× 速度:最低で、o(n^2) サンプルプログラム 200回、テスト[回数-1]は乱数(200) テストをおいこみソート。 テストをメモ記入。 おわり //本体 ●おいこみソート(Aを) max=配列要素数(A) max_S=0 min_S=0 iを0からINT(max/2)まで繰り返す max_S=max-i min_S=i kをiからmax-iまで繰り返す もし、A[k] A[max_S]なら、max_S=k もし、A[k] A[min_S]なら、min_S=k 最大値の交換 もし、max-i max_Sなら tmp=A[max_S] A[max_S]=A[max-i] A[max-i]=tmp 最小値の交換 もし、i min_Sなら tmp=A[min_S] A[min_S]=A[i] A[i]=tmp Aで戻る。 名前 コメント
https://w.atwiki.jp/aniwotawiki/pages/42646.html
登録日:2019/08/13 Tue 23 30 32 更新日:2023/07/07 Fri 09 34 36NEW! 所要時間:約 6 分で読めます ▽タグ一覧 TASさん専用 アルゴリズム ソート ボゴソート 数撃ちゃ当たる 欠陥品←可能性自体はある 複雑 適当にやってりゃいつかは終わる←乱数の取り方によっては…… 突然だが、この項目を見ているwiki篭り諸君は「ソート」というものをご存知だろうか? 分かりやすく言えばランダムに並べられたデータの集合を順番どおりに並べ替えるアルゴリズムの一つで、アルゴリズムの入門書などでは比較的早い段階で出る事が多い。 ボゴソートはその一種である。詳細について説明する前にまずアルゴリズムに関連する簡単な用語についてざっくりと説明しよう。 ①:計算量 簡単に言えばデータの集合に適用するアルゴリズムが始まってから終わるまでの計算の回数のこと。 基本的にアルゴリズムはコンピュータに対してプログラムと集合を準備し実装していくのだが、使用するコンピュータのメモリ等の関係上、計算量が多いとアルゴリズムを最後まで行えるか、行えるならどのくらいかかるかという問題が出てくる。 つまり計算量が小さいほどそのアルゴリズムは早く終わる事になる。 計算量と一口に行っても公式の様にガッチリ決まっているわけではないので、平均的にはどのくらいになるのかを考える「平均計算量」、これ以上遅くなる事はないという指標である「最悪計算量」、逆に理想的なパターンを表す「最良計算量」などの様々なパターンが考えられている。 ②:ランダウ記号 データの集合がn個の要素を持っていたとする。 その集合に対してアルゴリズムによる特定の処理を行う場合、計算量は基本的にnの値に影響される。 つまり計算量はnの関数で表現できるという事である。しかしその式が簡単とは限らない。 そこで役に立つのがランダウ記号である。簡単な定義を書くと「出てきたnの式P(n)が、nが十分大きい所では関数f(n)の定数倍より小さくなる時、P(n)=O(f(n))とする(*1)。」となる。 この定義では「なんのこっちゃ?」と思う人もいるかもしれないが、これに関しては「なるべく簡単な関数でnの式を大雑把に表現しちゃおう!」程度の認識で良い。 なお上の定義ではf(n)は条件さえ満たしていればいくらでも大きくしていいのだが、基本的には出来るだけ小さな関数を用いるのが通例である。 さて、これらを踏まえてボゴソートに戻る。 先ほど述べた通りソートは「与えられたデータの整序」が目的のアルゴリズムなのだがボゴソートの手順はと言うと……、 ①:与えられたn個のデータをバラバラにして、その後無作為に並べる。 ②:①で並べたデータの列が正しい並びになっていれば終了する。なっていなかった場合①に戻る。 なぁにこれぇ。 そう、このボゴソート、あまりにもいい加減すぎるアルゴリズムなのだ。 トランプ等のカードゲームで例えるなら、 ①:山札をシャッフルする。当然積み込みはなし。 ②:シャッフルしたカードを見てカード名があらかじめ決めておいた順番どおりに並んでいればソート完了。違っていればまたシャッフルをする。 名前もなかなか辛辣で「ボゴ」はbogus(インチキ・偽物)から来ており、monkey sort(猿でもできるソート)やshotgun sort(数撃ちゃあたるソート)などの変な別名もある。 通常、ソートを大雑把に分けると「実装は簡単だが時間のかかるソート」と「実装に多少手間がかかるが時間のかからないソート」に分かれる。 例を挙げると…… バブルソート ①:並べたn個のデータを左端から2つずつ見ていく。 ②:2つのデータの並びが反対ならば入れ替え、そうでなければそのまま。 ③:②の作業がデータの右端まで来たとき、並びが正しいならソート完了、違っていた場合、もう一度左端から見ていく。 クイックソート ①:n個のデータを並べた際に基準となる値を持つデータ(「ピボット」と言う。)を1つ選択する。 ②:ピボットの位置を基準にそれより大きいものと小さいもののグループにデータを分割する。 ③:分けたグループ内で簡単に実装できるソートを行う。 バブルソートは非常に実装が簡単だが、その分時間はかなりかかるソート、クイックソートは実装は多少面倒(*2)だが、計算時間は速いソートである。 n個のデータに対する計算時間について書くと…… 平均計算時間:バブルソート…O(n^2)、クイックソート…O(n log n) 最良計算時間:バブルソート…O(n)、クイックソート…O(n log n) 最悪計算時間:バブルソート…O(n^2)、クイックソート…O(n^2) となる。(log nはe(「自然対数の底」と言う数)がnと等しくなる為に必要な累乗の数を指す。) パッと見ても分かりにくいかもしれないが、log n(対数関数)は増加が途轍もなく遅い関数なので、nが大きいとこの関数の影響が大きくはたらいてくる。 と、ここまでは一般的なソートの話。 このボゴソートの場合の計算時間は以下の通り。 平均計算時間: O(n×n!)(*3) 最良計算時間: O(n) 最悪計算時間: O(∞) …うん、分かる人には分かるだろう。ものすごく遅い。 平均計算量の理屈としては「1回の並べ替え」にn回の操作、繰り返しの回数が期待値n!だけ行われるためにそのかけあわせでこのような値になる事になる事から決定する。 とは言え、これだけだとよく分からないかもしれないので、各ソートの平均計算量のランダウ記号の中の関数の値(*4)を見てみると・・・ n=5 n^2(バブルソート) → 25 n log n(クイックソート) → 8(*5) n×n!(ボゴソート) → 600 n=10 n^2(バブルソート) → 100 n log n(クイックソート) → 23 n×n!(ボゴソート) → 36288000 n=15 n^2(バブルソート) → 225 n log n(クイックソート) → 41 n×n!(ボゴソート) → 19615115520000 これ以上は止めておくが、nの増加でボゴソートの計算量が爆発的に増加している。 nの数が膨大になれば計算量が大きくなりすぎて、容量内での計算が極めて困難、あるいは不可能になってしまうこともあり得る。 こんなボゴソートだが、実は理論上有限回で終わる事が保証されている。 これは「無限の猿定理」という、「ランダムな文字の列を無限に長く作り続ければ、その中にどんな文字列も作れる」と言う定理による。 ……が、あくまで「理論上」である。 というのもこのアルゴリズム、一見ランダムに並べて一致しているかどうかを調べるだけなので実装は簡単そうに見えるが、この「ランダム」という点が曲者で、並べ替えの為の乱数をうまく発生させる必要があるので実際にはあまり簡単ではない。 この乱数生成についてだが、完全な乱数ではなく一見乱数に見えるが、実は数を決められた計算によってはじき出している「擬似乱数」というものを使う。上のシャッフルの例で言うならヒンドゥーシャッフルやディールシャッフル、ショット・ガン・シャッフルリフルシャッフルなどの方法の事と思えばいい。 これの作り方によってはランダム性が低く、計算がいつまでも終わらないという事態もあり得るからである。 また有限回と言っているだけでその値が計算機には扱えないレベルの途轍もなく大きい数になる可能性もある。 例えばそれは無量大数の様な数かもしれないし、10の100乗である1グーゴルかもしれない。 はたまた指数表記すらできないほどの巨大数であるグラハム数かもしれないし、それ以上かもしれない。 こうなった場合、計算をするコンピューターはひとたまりもない。 「理論上有限回で止まる」ことと、「有効なアルゴリズムである」こととの間には大きな隔たりがあるのだ。 こういった問題点を持つボゴソートだが、他のソートには見られない特徴として「並び替え後のデータの列が並び替え前のデータの列の状態に全く依存していない」という点が挙げられる。 基本的にソートは並び替えの前後の状態に関係があり、並び替え前の時点で整序がどの程度完成してるかが結果にも影響してくる。(詳しくは触れないが「ソート自体が安定かそうでないか」も関係してくる。) が、ボゴソートにはそういったものがない為、運がよければ1回目の並び替えであっという間に終わってしまうという事もあり得る。 勿論データ数が増えてしまうと、それも容易ではなくなるのだが、この点も乱数の生成方法によっては上手く行きやすくなる。 変な性質を持つボゴソートだが、乱数の作り方次第では非常にいいソートとなりうるという可能性を秘めたソートでもあるのだ。 追記・修正は全文をランダムに並べ替えて整序が住んでいるか確認しながらお願いします。 △メニュー 項目変更 この項目が面白かったなら……\ポチッと/ -アニヲタWiki- ▷ コメント欄 [部分編集] この項目はアレか、「誰か無限の猿定理の項目を作れ」ということなのか。 -- 名無しさん (2019-08-13 23 51 25) 量子コンピュータなら最強説ある -- 名無しさん (2019-08-14 00 17 16) 名前 コメント
https://w.atwiki.jp/kyo20090608/pages/38.html
編集 そうです、 そうっとソートいたしましょう。 (コラ ソートの種類ですか? たくさんありますよ。 wikiを見ればわかりますが さて、次の種類が主なソートです。 バブルソート 選択ソート 挿入ソート シェルソート(挿入ソートの改良) マージソート(分割統治) ヒープソート クイックソート 基数ソート(バイナリソート) [1]バブルソートは、頭からスタートして 隣を比較しながら、ソートしていきますね。 これ、一般人のする並べかえと同じです。 小学生もやるんではないでしょうか? 先頭と次を比べて交換していくの すごいじかんが かかるけど 計算量の単位オーダを用いると 平均計算量は、なくて いつでも、O(n^2)です。 ちなみに”^”ってのは、累乗です。 基本ですね バブルソートソース なんか、いろいろ、こってたら時間たつんで つぎ! [2]セレクションソートです。 選択ソートです。 バブルは、全部比較して交換してを繰り返しますが。 選択は、選択します。 n=10の場合 1~10番目を見て、最小の値を配列の1番目に入れます。 次は、それを除くn=9の中の1~9番目を見て 最小の値を配列の2番目に入れます。 これを繰り返します。 バブルと似たソースになりますが オーダーは 最悪平均ともにO(n^2)です。 通常安定してますが 安定感を除くこともできます。 [3]インサートソート(挿入ソート) ほぼ並んでいる列には強いので クイックソートされた列のどこかに値を挿入し それをソートする時に用いる方法 値を挿入し、挿入した値に対して 大きいか小さいかによって左右に振り分ける 選択ソートに比べて、比較回数が少なくなる 平均O(n+d)※dは、置換のときの反転数 最悪O(n^2) [4]シェルソート シェル ラルクアンシエルとは、ちがうか D.L.SHELLさんが考案したアルゴリズム 大きいか小さいかで大雑把にソートして それを挿入ソートで仕上げる。 最悪O(nlog^2n) [5]マージソート 配列の分割を行い、配列数がn=2以下になったときに 比較し、すべて比較し終わったら 配列をくっつけながら、比較していく。 分割統治法とも言う。 平均最悪ともにO(nlogn)である。 安定している。 [6]ヒープソート 木構造を用いて行う。 topが最小で bottomが最大になるような木をヒープという。 [7]クイックソート [8]基数ソート
https://w.atwiki.jp/mopsprogramming/pages/150.html
もう一つソートをやってみました。自分でもできそうなやつ、ということでコムソートにしました。虚無僧と、じゃないです(||_ _)。コームとか、コウムの方が近いですか。コム(Comb)は、くし(櫛)のことらしいです。クシで鋤いていく感じからそういわれるようです。「隣同士を比べて並び替える」を何度も繰り返すバブルソートと呼ばれる方法の改良版なのだそうですが、動作が速い上にメモリーもあまり使わないのだそうです。コードも単純ですから、ま、優秀なソートですね。1990年頃に開発された、ソートとしては新しいものらしいです。 手順は単純です。まず、リストの全長を1.3で割って(小数点以下切り捨て)、それをギャップに設定します。そして、そのギャップの分だけ離れた場所にある2要素を比較して、逆順だったら入れ替えるという処理を繰り返します。左端から順に、ずらしていって、右側が端に当たってギャップが取れなくなったところで終わりです。次に、ギャップをまた1.3で割って、新しいギャップとして、同じことを繰り返します。ギャップが0になったら、最後の仕上げとして、バブルソートをかけます。バブルソートは遅いのが欠点なのですが、もうあらかた揃っているので、ほとんど時間はかかりません。1000個のリストでためしてみると、大低あと一回で全部揃います。30000でも7回くらいのようです。 "1.3で割る"というのは怪しげですが、この値は経験的に決められたものらしいです。だんだんとギャップを狭めていくことを、クシの目を細かくしていく、と考えるようです。 単純に比較回数を減らそうとしたら、ギャップを割る定数を大きくすればいいわけですが、まず、最低限1より大きくないといけません。で、3項目リストのことを考えたら、1.5以下じゃないと、整列できません(ってことはないな、バブルソートになってしまう、ってことですか。)。というふうに考えていくと、上限がだんだん下がってきそうですが、1.3付近に収束するんですかね。やってみると、ギャップが0になった時点での整理漏れが1.3くらいで一番少ないようです。 さて、Mopsで実装です。普通にやってもアレなので、普通じゃない手を二つ使いました。ひとつは、1.3で割るときに浮動小数点数を使わなかったこと。もう一つは、Local Sectionを使ったことです。前者は多分、かえって遅くなるやり方ですが、後者は速くなる手だと思います。ま、浮動小数点数の回避のやり方は、固定小数点数の計算方法で、昔、コンピュータが小数が苦手だった頃は、普通に使われていた方法だと思いますが。 LOCAL SECTIONというのは、Mops特有の技巧です。局所変数をセクション内の複数のワードで共有できるようにする方法です。MopsはC言語系のライブラリ関数を呼んだりするせいで、局所変数を長い間保持しておきたいという事態が起こりやすいようです。局所変数は1ワードの間有効ですから、長ーいワードを定義すればいいわけですが、それはコードを読みにくくし、保守を難しくします。大域変数を使えばいいともいえますが、局所変数がレジスタ変数で効率がいいことを考えると、局所変数が何らかの形で保持できれば、それに越したことはないといえます。かくして、Local Sectionが実装された、ということのようです。 ですから、Local Sectionは、そのセクション全体が一つのワードであると考えるとわかりやすいでしょう。一つのワードを、外見上、複数のワードに区切って定義することができる、と。実際、本体であるワード以外のセクション内のワードは、セクションの外から呼び出すことはできません。セクション内では自由に呼び合うことができます。まあ、後方で定義されているワードを呼び出すのには工夫が要りますが。また、セクション内のワードがセクション外のワードを呼び出すのは自由です。 Mopsマニュアルでは、Local Sectionは固有のテンポラリオブジェクトを持つことができるように書かれていますが、Carbon PowerMops以降は、これはできなくなっています。ま、ちょっと残念ですが、あまり必要にならないので、私はそれほど気にしていません(^^;;)。 追記:PowerMops 5.6から、この点はマニュアル通りに動くようになりました!つまり、2005年以降はローカルセクションが固有のテンポラリオブジェクトを持つことができます。メソッドのローカルセクションについても同じです。 前置きが長くなりました。コードを見ましょう。 まず、 ObjPtr Numbers class_is Ordered-Col Local CombSort { \ left right size pitch yet -- } ..... はじめの1行は、与えられるリストのポインタを格納するためのObjPtrです(マージソートを参照)。次のコードから、ローカルセクションが始まります。まず、Localと書いて、その後に"セクション名"、そしてMopsの標準的なやり方での"局所変数の宣言"を書きます。名前付きパラメターを持つこともできます。要するに、このセクション名のワードを一つ定義するのだと考えてもいいです。 続いて、セクション内部的なワードを定義していきます。 Comb BEGIN right size WHILE left at numbers right at numbers \ -- lv rv 2dup IF \ if left right, interchange values left to numbers right to numbers true - yet ELSE \ if left = right, do nothing 2drop THEN 1 dup ++ left ++ right \ paralell transposition REPEAT ; 怪しげな英語のコメントも付けてみました。コメントも説明が必要ですね(^^;;)。名前のCombは「くし」という名詞のつもりじゃなくて、「くしけずる」とか「鋤く」とか、動詞のつもりでした。"right"、"left"、"size"は全部局所変数ですね。セクション内の別のワードで設定されて、ここにやってきます。 この"くし"は二本歯です。"left"が左の歯、"right"が右の歯です。後で出てくる"pitch"の分だけ間が空いています。この「くし」を、与えられたリストに当てて、値を二つ掻き出します。はじめは左に歯をリストの左端に合わせます。スタックには、左、右の順で積み込みます。 次に"2dup"でこの二つの値をコピーしてその大きさを比べます。左に小さい方を置きたいので、もし右の方が小さかったら、リストの値を入れ替えます。スタックは、上の方が右の値ですから、「左、右」と押し込めば入れ変わります。逆順じゃないときには、何もしません。余分な値は"2drop"で落としておきます。 なお、値を交換したときには、局所変数"yet"を"TRUE"にしていますが、これは後でバブルソートに使うためのものです。 そして、「くし」を一つだけ右に平行移動して、また同じようにくしけずります。これをずーっとやって、右の歯がリストの右端に当たるまで続けます。 次のコードは: BUBBLE BEGIN 0 - left 1 - right false - yet comb yet NUNTIL ; これは、最後の仕上げに使うバブルソートです。要は、ピッチ(ギャップ)を1に固定したコムソートで、もう逆順がなくなるまで、何回でもかけるわけです。はじめに"false"にセットした"yet"が、もし逆順があれば"true"になって帰ってきますから、「ならもう1回」となるわけです。逆順がなくなれば、"yet" は"false"のままで帰ってきますから、ループを抜けて終了です。 さあ、本体です。 LOC CombSort ( ^obj -- ) \ { \ left right size pitch yet -- } - numbers limit numbers dup - size 10 * 13 / - pitch BEGIN pitch 0 WHILE 0 - left pitch - right comb pitch 10 * 13 / - pitch REPEAT BUBBLE ;LOC ここで、このセクションは大団円を迎えます。この本体ワードの定義は、普通の、コロン、セミコロンではなくて、" LOC"で始め、";LOC"で終わることになっています。そして、セクションの最後に来ます。 このワードは、Ordered-Colクラスのリストのポインタを引数としてとります。まずそれを、"numbers"に格納します。そして、"Limit "メッセージでリスト全体の大きさをとります。これは、局所変数"size"に格納されると同時に、"1.3"で割って局所変数"pitch"に格納されます。 このpitchが「くし」の目のサイズを決めるもので、一応、最初の目が決まるわけです。 1.3で割るために、10を掛けてから13で割っています。こういうやり方をすると、大きな数値が来たときには、10を掛けた時点で桁が限界をはみ出してしまい、正しい結果が得られない場合もあります。ですが、今の場合には、Ordered-Colクラスのサイズの限界が2バイト整数なので、この範囲なら桁がはみ出してしまう虞れはありません。もっと大きいサイズのリストをソートしたいなら、別のクラスを定義してつくることになるでしょう。そのときには、素直に浮動小数点数を使えば大丈夫です。 次のループですることは、"left"を左端にセットし、ピッチの分離れた値に"right"をセットした上で「くしけずり(Comb)」ます(^^;;)。戻ってきたら、"pitch"をまた1.3で割って、目を細かくして、同じことを繰り返します。"pitch"が0になったら、このループは終わりです。 最後の仕上げに"BUBBLE"をかけます。 体感的には、確かにマージソート並には速い感じですが、多分、項目数を相当大きくしないと、体感じゃわからないでしょうね(^^;;)。小さいリストならバブルソートでも差はないでしょうね。コムソートの改良版というのもあるそうで、"pitch"が9か10になったときはその後のしくじりが多くなって最後のバブルソートに負担がかかって遅くなるので、そのときには無理矢理11にしてしまうのだそうです。ま、簡単に変えられますよね。 トップページへ 目次へ
https://w.atwiki.jp/hogazurou/pages/102.html
手法 私たちがランダムに並んだ数字を順に並べろ、と 命令されたときにどのような手順で行うか考えて欲しい。 おそらく、バブルソートのような方法を考えた方はほとんど いないのではないだろうか?そそいてこの挿入ソートこそが、 人の考える並び替えに最も近いのではないかと思う。 手法 図を見ながら解説します。 すでに並び終わっている部分を黄色にして、並び替え(動かし)た 部分を矢印であらわしています。 やり方 順に数字を見ていって、今見ている数はすでに並び終わっている部分で どこに入るかをみて、入れる。これを文字数回繰り返すとすべての数が 並び終わる。
https://w.atwiki.jp/magicman/pages/7903.html
偶発のバブルソーサー C 火文明 (4) クリーチャー:ブレイブ・スピリット 2000 ■自分のティラノ・ドレイクまたはブレイブ・スピリットはすべて、アンタップされているクリーチャーを攻撃できる。 作者:テーメノン フレーバーテキスト 一心不乱に、回りながら燃え広がる! 評価 名前 コメント
https://w.atwiki.jp/bonchu/pages/27.html
ソートアルゴリズム ある数字列を並び替えるにはどのようなアルゴリズムがあるだろうか。 クイックソート 一番左の数字を基準にそれより大きいほうと小さいグループに分ける。分けたグループ内で同じことをし、グループが全て単体になったらソート完了 最も早い。標準Nlog(N)、最大N^2 マージソート 要素を分割していき、単体から順にソートしながらマージしていく。 比較的早い。標準・最大Nlog(N) ヒープソート 挿入ソート バブルソート 一番左の数字と二番目の数字を比較し、大きいほうを右側にする。次に二番目と三番目で同じことを行い、三番目と四番目、四番目と五番目とソートしていく 最も単純で遅い
https://w.atwiki.jp/magicman/pages/15157.html
プリズン・バブルソープ P 水文明 (2) クリーチャー:スプラッシュ・クイーン 2000 ■相手が自身のマナゾーンからカードを手札に加える時、かわりに持ち主の山札に加えてシャッフルする。 作者:切札初那 フレーバーテキスト シャボン玉飛んだ♪敵まで飛んだ♪ ――シャボン・メルメイジ 収録 NDMV-01 決戦!冒険vsランデス! 名前 コメント
https://w.atwiki.jp/nina_a/pages/17.html
ソートアルゴリズムの実装 このページを編集 バブルソート もっとも直感的なソートアルゴリズム void BubbleSort(int data[], const int len){ for(int max = len-1; max 0; --max){ for(int k = 0; k max; ++k){ if(data[k] data[k+1]){ int tmp; tmp = data[k+1]; data[k+1] = data[k]; data[k] = tmp; } } } } セレクションソート バブルソートの改良版 void SelectionSort(int data[], const int len){ int m, tmp; for(int max = len; max 0; --max){ m = 0; for(int k = 1; k max; ++k){ if(data[m] data[k]){ m = k; } } tmp = data[max]; data[max] = data[m]; data[m] = tmp; } } クイックソート 実用上で最も早い void QuickSort(int data[], const int low, const int high){ if(low high){ // ピボットの決定 int x = (data[low] + data[high] + data[(low+high)/2])/3; int left = low - 1, right = high + 1; while(left = right){ while(data[++left] x); while(data[--right] x); if(left right) Swap( data[left], data[right]); } QuickSort(data, low, right); QuickSort(data, left, high); } } 各アルゴリズムの実行時間(実測) 以下は課題でソートにかかる時間を実測した結果である。なお、当時のCPU利用時間制限上、ソートに3分以上かかる物については-と表記した。 データ数 バブルソート セレクションソート クイックソート 基数ソート 10000 1.207 0.698 0.003 0.005 20000 4.830 2.790 0.006 0.011 30000 10.85 6.281 0.009 0.018 40000 19.31 11.16 0.012 0.022 50000 30.18 17.44 0.015 0.028 60000 43.49 25.18 0.018 0.034 70000 59.22 34.25 0.021 0.041 80000 77.49 44.88 0.025 0.045 90000 98.25 57.25 0.028 0.054 100000 121.3 70.22 0.031 0.057 200000 - - 0.065 0.115 300000 - - 0.099 0.172 400000 - - 0.134 0.228 500000 - - 0.169 0.290 600000 - - 0.206 0.343 700000 - - 0.255 0.406 800000 - - 0.290 0.467 900000 - - 0.347 0.541 1000000 - - 0.358 0.649 カテゴリ:C/C++